#include<iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>
using namespace std;

int massage(vector<int>& nums) {
    if (nums.size() == 0) return 0;

    int n = nums.size();
    vector<int> f(n), g(n);
    f[0] = nums[0], g[0] = 0;
    for (int i = 1; i < n; i++)
    {
        f[i] = g[i - 1] + nums[i];
        g[i] = max(g[i - 1], f[i - 1]);
    }
    return max(f[n - 1], g[n - 1]);
}

int rob(vector<int>& nums) {
    if (nums.size() == 0) return 0;
    if (nums.size() == 1) return nums[0];

    int n = nums.size();
    vector<int> f1(n), g1(n), f2(n), g2(n);
    f1[0] = nums[0];

    g1[1] = max(f1[0], g1[0]);
    for (int i = 2; i < n - 1; i++)
    {
        f1[i] = g1[i - 1] + nums[i];
        g1[i] = max(f1[i - 1], g1[i - 1]);
    }

    f2[1] = nums[1];
    for (int i = 2; i < n; i++)
    {
        f2[i] = g2[i - 1] + nums[i];
        g2[i] = max(f2[i - 1], g2[i - 1]);
    }

    return max({ f1[n - 2], f2[n - 1], g1[n - 2], g2[n - 1] });
}
int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
    unordered_map<int, int> hash;
    for (auto& x : arr)
    {
        hash[x]++;
    }
    vector<pair<int, int>> v(hash.begin(), hash.end());
    sort(v.begin(), v.end(), [](auto& a, auto& b) {
        return a.second < b.second;
        });
    int ret = v.size();
    /*for (auto [key, val] : v)
    {
        if (k >= val)
        {
            k -= val;
            --ret;
        }
        else break;
    }*/
    vector<pair<int, int>>::iterator it = v.begin();
    for (; it != v.end(); it++)
    {
        if (it->second <= k) k -= it->second, --ret;
        else break;
    }
    return ret;
}
int main()
{
    vector<int> v{ 3,3,3,4,4,4,5,5,5 };
    massage(v);
    rob(v);
    findLeastNumOfUniqueInts(v, 3);
	return 0;
}